package likou.dtgh.beibao;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/12 08:00
 * 完全背包问题
 */
public class _1449 {

    public static void main(String[] args) {
        System.out.println(largestNumber2(new int[]{29,60,55,90,90,92,61,32,55}, 602));
    }

    public static String largestNumber(int[] cost, int target) {
        //stones[i][0]：石头大小，stones[i][1]：石头价值
        List<int[]> list = new ArrayList<>();
        int[] stones = new int[5000];
        //石头数量最多的情况下保证石头的价值最高。
        //下面保证了石头价值最高
        for (int i = cost.length - 1; i >= 0; i--) {
            if (stones[cost[i]] == 0) {
                list.add(new int[]{cost[i], i + 1});//大小,价值
            }
            stones[cost[i]] = i + 1;
        }
        //排序完成
        list.sort((int[] i1, int[] i2) -> i1[0] == i2[0] ? i1[1] - i2[1] : i1[0] - i2[0]);
        String res = dfs(list, target, 0, "");
        if (res == null) {
            return "0";
        }
        sortStr(res);
        return res;
    }

    /**
     * @param list 遍历对象
     * @param now  差多少大小
     * @param i    当前遍历到第几位
     * @param str  当前字符串
     */
    public static String dfs(List<int[]> list, int now, int i, String str) {
        if (now == 0) {
            return str;
        }
        String res = null;
        for (; i < list.size(); i++) {
            int size = list.get(i)[0];
            int value = list.get(i)[1];
            if (now % size == 0) {
                if (res!=null){
                    return maxStr(sortStr(getStr(str, value, now / size)), res);
                }else {
                    return sortStr(getStr(str, value, now / size));
                }
            }
            if (now / size < 2) {
                continue;
            }
            if (size > now) {
                return null;
            }
            for (int p = now / size - 1; p > 0; p--) {
                String nowStr = sortStr(dfs(list, now - p * size, i + 1, getStr(str, value, p)));
                if (nowStr != null) {
                    if (res == null) {
                        res = nowStr;
                    } else {
                        res =maxStr(res,nowStr);
                    }
                }
            }
        }
        return res;
    }

    public static String getStr(String str, int integer, int num) {
        StringBuilder sb = new StringBuilder(str);
        for (int i = 0; i < num; i++) {
            sb.append(integer);
        }
        return sb.toString();
    }

    public static String sortStr(String res) {
        if (res == null || res.isEmpty()) {
            return null;
        }
        char[] chars = res.toCharArray();
        Arrays.sort(chars);
        res = new StringBuilder(new String(chars)).reverse().toString();
        return res;
    }

    public static String maxStr(String str1, String str2) {
        if (str1.length()>str2.length()){
            return str1;
        }
        if (str1.length()<str2.length()){
            return str2;
        }
        return str1.compareTo(str2)>0?str1:str2;
    }


    /**
     *
     * 
     * @param cost
     * @param target
     * @return
     */
    public static String largestNumber2(int[] cost, int target) {
        int[] dp = new int[target + 1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        for (int c : cost) {
            for (int j = c; j <= target; ++j) {
                dp[j] = Math.max(dp[j], dp[j - c] + 1);
            }
        }
        if (dp[target] < 0) {
            return "0";
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 8, j = target; i >= 0; i--) {
            for (int c = cost[i]; j >= c && dp[j] == dp[j - c] + 1; j -= c) {
                sb.append(i + 1);
            }
        }
        return sb.toString();
    }
}
